#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
double max_v;
double f[2000][2000];
char t[2000], s[2000], ans[2000];
int from[2000][2000], c[2000][2000], d[2000][2000];
struct alignas(16) Node
{
    char c;
    size_t num;
    Node *fail;
    Node *to[10];
    int cnt;
    double val;
} root;
vector<Node *> arr{&root};
int main()
{
    freopen("magic.in", "r", stdin);
    freopen("magic.out", "w", stdout);
    scanf("%d%d%s", &n, &m, t);
    for (int i = 0, v; i < m; i++)
    {
        scanf("%s%d", s, &v);
        Node *x = &root;
        double val = log(v);
        for (int j = 0; s[j]; j++)
        {
            if (!x->to[s[j] - '0'])
            {
                arr.push_back(x->to[s[j] - '0'] = new Node{s[j], arr.size(), x});
            }
            x = x->to[s[j] - '0'];
        }
        x->val += val;
        x->cnt++;
    }
    queue<Node *> q({&root});
    while (q.size())
    {
        Node *x = q.front();
        q.pop();
        if (x != &root)
        {
            Node *y = x->fail->fail;
            x->fail = &root;
            while (y)
            {
                if (y->to[x->c - '0'])
                {
                    x->fail = y->to[x->c - '0'];
                    x->val += x->fail->val;
                    x->cnt += x->fail->cnt;
                    break;
                }
                y = y->fail;
            }
        }
        max_v = max(max_v, x->val);
        for (Node *y : x->to)
        {
            if (y)
            {
                q.push(y);
            }
        }
    }
    int len = strlen(t);
    double l = 0, r = 2 * max_v * len;
    fill(f[0] + 1, f[0] + arr.size(), -1e8);
    while (clock() < 0.9 * CLOCKS_PER_SEC)
    {
        double val = (l + r) / 2;
        ++cnt;
        for (int i = 0; i < len; i++)
        {
            fill(f[i + 1], f[i + 1] + arr.size(), -1e8);
            for (int j = 0; j < int(arr.size()); j++)
            {
                for (int k = t[i] == '.' ? 0 : t[i] - '0'; (t[i] == '.' && k < 10) || k == t[i] - '0'; k++)
                {
                    Node *x = arr[j];
                    while (x != &root && !x->to[k])
                    {
                        x = x->fail;
                    }
                    x = x->to[k] ? x->to[k] : &root;
                    if (d[i + 1][x->num] != cnt || f[i][j] + x->val - x->cnt * val > f[i + 1][x->num])
                    {
                        f[i + 1][x->num] = f[i][j] + x->val - x->cnt * val;
                        from[i + 1][x->num] = j;
                        c[i + 1][x->num] = k;
                        d[i + 1][x->num] = cnt;
                    }
                }
            }
        }
        r = val;
        for (int i = 0; i < int(arr.size()); i++)
        {
            if (d[len][i] == cnt && f[len][i] > 0)
            {
                r += val - l;
                l = val;
                for (int j = len; j; j--)
                {
                    ans[j - 1] = c[j][i] + '0';
                    i = from[j][i];
                }
                break;
            }
        }
    }
    puts(ans);
    return 0;
}